\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

\title{作业二: 二叉搜索树排序的实现}


\author{夏知人 \\ 信息与计算科学 3210103669}

\begin{document}

\maketitle


\section{代码概括}
通过构建一棵二叉搜索树，先设置一个根节点，再将后输入的数据与根节点比较大小。将比根节点大的数值连接在右子树，比根节点小的数值连接在左子树。这样不断重复此过程，构建出的树每个根节点
最多含有两个子节点，且左子树上的所有数据都小于根节点，右子树上的数据都大于根节点。

\section{成员函数及其设计思路}
定义BinarySearchTree类，该类包含以下成员函数：\par
findMin()：不断寻找制定节点的左侧子节点，通过不断递归，找到某个节点不再有左侧子节点，那么该节点就是要找的最小的节点，返回该节点。\par
findMax()：不断寻找制定节点的右侧子节点，通过不断递归，找到某个节点不再有右侧子节点，那么该节点就是要找的最小的节点，返回该节点。\par
contains()：通过将要查找的数与节点数值比较大小，判断要查找的数在该节点的左子树上还是右子树上。不断迭代该过程，最后若最后一个节点并不等于要查找的数，则返回0；若成功找到了要查找的数，则返回1。\par
makeEmpty()：清空这棵树的所有节点。\par
isEmpty()：判断这棵树是否为空。\par
insert()：先顺着树进行查找，如果找到了要插入的数x，则什么都不做。若没有找到要插入的数，则将要插入的数x连接在根节点的对应叶子节点上。\par
remove()：删除某个节点要分为三种情况。若要删除的节点是叶子节点，则可以直接删除该节点；若要删除的节点有一个子节点，则将其根节点的对应指针指向要删除的节点的子节点；
                  若要删除的节点有两个子节点，则使用其右子树的最小的数据代替该节点的数据并递归地删除那个节点，因为右子树中的最小的节点不可能有更小的子节点，所以第二次删除可以按照前两种的情况\par


\section{树上节点结构}
定义树上节点的结构，该结构包含储存的数据，左侧子节点，右侧子节点。相关代码实现如下：
\begin{verbatim}
struct BinaryNode
	{
		Comparable element;
		BinaryNode* left;
		BinaryNode* right;

		BinaryNode(const Comparable& theElement,BinaryNode* lt,BinaryNode* rt):element(theElement),left(lt),right(rt){}
	};

	BinaryNode* root;

	void insert(const Comparable& x, BinaryNode*& t)const;
	void remove(const Comparable& x, BinaryNode*& t)const;
	BinaryNode* findMin(BinaryNode* t)const;
	BinaryNode* findMax(BinaryNode* t)const;
	bool contains(const Comparable& x, BinaryNode* t)const;
	void makeEmpty(BinaryNode*& t);
	void printTree(BinaryNode* t)const;
	BinaryNode* clone(BinaryNode* t)const;
\end{verbatim}

\section{排序功能代码}
当传入的$_mode$为0时，通过将给入的数据依次放入二叉搜索树，实现对传入数据按大小的有序排列，再不断将二叉搜索树中最小的数据插入原先的动态数组，再删除树中最小数值的节点，不断迭代次过程，
实现将动态数组中的数据按照从小到大的顺序进行排列。最后使用makeEmpty()函数清空整棵树中的节点与数据，避免内存泄漏。当传入的_mode为1时，使用std::random_shuffle()对数组进行乱序，然后重复
当$_mode$为0时的操作过程。排序功能的代码实现如下：
\begin{verbatim}
template<typename Comparable>
void BSTsorting(std::vector<Comparable>& _arr, int _mode)
{
	BinarySearchTree<int> Tree;
	int size = _arr.size();
	if (_mode == 0) {
		for (int i = 0; i < size; i++) {
			Tree.insert(_arr[i]);
		}
		for (int i = 0; i < size; i++) {
			_arr[i] = Tree.findMin();
			Tree.remove(_arr[i]);
		}
		Tree.makeEmpty();
	}
	if (_mode == 1) {
		std::random_shuffle(_arr.begin(), _arr.end());
		for (int i = 0; i < size; i++) {
			Tree.insert(_arr[i]);
		}
		for (int i = 0; i < size; i++) {
			_arr[i] = Tree.findMin();
			Tree.remove(_arr[i]);
		}
		Tree.makeEmpty();
	}
}
\end{verbatim}

\section{测试程序}
通过将 1 到输入的 n 共计 n 个数字输出，写入到 test.in 文件，测试程序使
用文件重定向输入数据即可。将 1 到输入的 n 共计 n 个数字输出，写入到
data.in 文件。测试程序的代码实现如下：
\begin{verbatim}
std::vector<int> a;
int n, x;
int main() {
	clock_t startTime, endTime;
	freopen("test.in", "r", stdin);
	std::cin >> n;
	for (int i = 1; i <= n; i++) {
		std::cin >> x;
		a.push_back(x);
	}
	std::cout << "_mode = 0" << std::endl;
	startTime = clock();
	BSTsorting(a, 0);
	endTime = clock();
	std::cout << "The run time is: " << (double)(endTime - startTime) << "ms" << std::endl;

	std::cout << "_mode = 1" << std::endl;
	startTime = clock();
	BSTsorting(a, 1);
	endTime = clock();
	std::cout << "The run time is: " << (double)(endTime - startTime) << "ms" << std::endl;

	return 0;
}
\end{verbatim}


\end{document}
